The even–odd rule is an algorithm implemented in vector-based graphic software, like the PostScript language, which determines how a graphical shape with more than one closed outline will be filled. Opposite: nonzero-rule.
The SVG specification says: "This rule determines the "insideness" of a point on the canvas by drawing a ray from that point to infinity in any direction and counting the number of path segments from the given shape that the ray crosses. If this number is odd, the point is inside; if even, the point is outside."
The rule can be seen in effect in many vector graphic programs (like Freehand or Illustrator), where a crossing of an outline with itself causes shapes to fill in strange ways.
On a simple curve, the even–odd rule reduces to a decision algorithm for the point in polygon problem.
bool
IsInside( const PointType & point, const PolygonType & polygon) const
{
int numpoints = polygon->NumberOfPoints();
int X=0;
int Y=1;
if(numpoints < 3)
{
return false;
}
const PointListType & points = polygon->GetPoints();
typename PointListType::const_iterator it = points.begin();
typename PointListType::const_iterator itend = points.end();
itend--;
PointType first = (*it).GetPosition();
PointType last = (*itend).GetPosition();
// If last point same as first, don't bother with it.
if( polygon->IsClosed() )
{
numpoints--;
}
bool oddNodes = false;
PointType node1;
PointType node2;
for(int i = 0; i < numpoints; i++)
{
node1 = (*it).GetPosition();
it++;
if(i == numpoints - 1)
{
node2 = first;
}
else
{
node2 = (*it).GetPosition();
}
const double x = point[X];
const double y = point[Y];
if((node1[Y] < y && node2[Y] >= y) ||
(node2[Y] < y && node1[Y] >= y))
{
if( node1[X] + (y – node1[Y])/
(node2[Y] – node1[Y]) * (node2[X] – node1[X]) < x )
{
oddNodes = !oddNodes;
}
}
}
return oddNodes;
}